package com.zjw.algorithm;

import com.zjw.algorithm.utils.TreeNode;
import com.zjw.algorithm.utils.Utils;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
 * <p>
 * 对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
 * <p>
 * 二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
 * <p>
 * 返回二叉树的 垂序遍历 序列。
 */
public class Solution17_2 {

    public static void main(String[] args) {
        System.out.println(new Solution17_2().verticalTraversal(Utils.createFullBinaryTree(new int[]{1, 2, 3, 4, 6, 5, 7})));
    }

    private static class Item implements Comparable<Item> {
        int col;
        int row;
        int value;

        public Item(int col, int row, int value) {
            this.col = col;
            this.row = row;
            this.value = value;
        }

        @Override
        public String toString() {
            return "(" + row + "," + col + ")";
        }

        @Override
        public int compareTo(Item o) {
            if (o.row == this.row) {
                if (this.value == o.value) {
                    return 0;
                }

                return this.value < o.value ? -1 : 1;
            }
            return this.row < o.row ? -1 : 1;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        Map<Integer, List<Item>> record = new HashMap<>();


        verticalTraversalImpl(0, 0, root, record);

        //解析record
        List<List<Integer>> result = new ArrayList<>();
        Set<Integer> keySet = record.keySet();
        keySet.stream().sorted().forEach(key -> {
            result.add(record.get(key).stream().sorted().map(item -> item.value).collect(Collectors.toList()));
        });

        return result;
    }

    private void verticalTraversalImpl(int col, int row, TreeNode node, Map<Integer, List<Item>> record) {
        List<Item> list = record.computeIfAbsent(col, integer -> new ArrayList<>());

        list.add(new Item(col, row, node.val));

        if (node.left != null) {
            verticalTraversalImpl(col - 1, row + 1, node.left, record);
        }

        if (node.right != null) {
            verticalTraversalImpl(col + 1, row + 1, node.right, record);
        }
    }
}
